import java.awt.*;
import java.util.List;

public class Test1 {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(){

        }
        public ListNode(int val) {
            this.val = val;
        }
    }

    public void addHead(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.println(cur.val + " ");
            cur = cur.next;
        }
    }

    public ListNode head;

    public ListNode removeElements(int val) {
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }

        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }

    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            if (fast.next == null) {
                break;
            } else {
                fast = fast.next.next;
            }
            slow = slow.next;
        }
        return slow;
    }
    public ListNode removeNthFromEnd(int n) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        if (n == 1) {
            head = head.next;
        }
        int count=0;
        ListNode tmp=head;
        while(tmp!=null){
            count++;
            tmp=tmp.next;
        }
        for (int i = 0; i < count- n+1; i++) {
            cur = cur.next;

        }
        ListNode curN = cur.next;
        if (curN.next == null) {
            cur.next = null;
        } else {
            cur.next = curN;
        }
        return head;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head=new ListNode();
        ListNode tmp=head;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                tmp.next=list1;
                list1=list1.next;
                tmp=tmp.next;
            }else{
                tmp.next=list2;
                list2=list2.next;
                tmp=tmp.next;
            }
        }
        if(list1==null){
            tmp.next=list2;
        }
        if(list2==null){
            tmp.next=list1;
        }
        return head;
    }
    public ListNode partition(int x) {
        ListNode ap = null;
        ListNode an = null;
        ListNode bp = null;
        ListNode bn = null;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                if (ap == null) {
                    ap = an = cur;
                } else {
                    an.next = cur;
                    an = an.next;
                }
            } else {
                if (bp == null) {
                    bp = bn = cur;
                } else {
                    bn.next = cur;
                    bn = bn.next;
                }
            }
            cur = cur.next;
        }
        if (ap == null) {
            return bp;
        }
        an.next = bp;
        if (bn != null) {
            bn.next = null;
        }
        return ap;
    }
    public boolean chkPalindrome(ListNode A) {
        ListNode fast=A;
        ListNode slow=A;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    public boolean chkPalindrome() {
        if(head==null){
            return true;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curN;
        }
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow){
                return true;
            }
            head= head.next;
            slow=slow.next;
        }
        return true;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA=1;
        int lenB=1; ListNode tempA = headA, tempB = headB;
        while (headA.next != null) {
            headA = headA.next;
            lenA++;
        }
        while (headB.next != null) {
            headB = headB.next;
            lenB++;
        }
        headA = tempA;
        headB = tempB;
        if (lenA > lenB) {
            for (int i = lenB; i < lenA; i++) {
                headA = headA.next;
            }
        }
        if (lenB > lenA) {
            for (int i = lenA; i < lenB; i++) {
                headB = headB.next;
            }
        }
        if (headA == headB) return headA;
        while (headA.next != null) {
            headA = headA.next;
            headB = headB.next;
            if (headA == headB) return headA;
        }
        return null;
    }
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        if(head==null){
            return false;
        }
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }

}
